package leetcode.editor.cn.q1_300.q50;

import java.util.Arrays;

/**
 * @author qidi
 * @date 2021-12-09 14:45:59
 */
class Q0057_InsertInterval {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] insert(int[][] intervals, int[] newInterval) {
            if (intervals.length == 0) return new int[][]{newInterval};

            int m = -1;
            int n = -1;
            for (int i = 0; i < intervals.length; i++) {
                if (intervals[i][0] <= newInterval[1] && intervals[i][1] >= newInterval[0]) {
                    if (m == -1) m = i;

                    intervals[m][0] = Math.min(intervals[m][0], newInterval[0]);
                    intervals[m][1] = Math.max(intervals[i][1], newInterval[1]);
                }
                if (intervals[i][0] > newInterval[1]) {
                    n = i;
                    break;
                }
            }

            /**
             * 两种情况：
             * 1 newInterval 和其他的范围不覆盖，只需要在插入就行，这种情况 m = -1，n 又分 2 钟情况：
             *      - n = -1，说明 n 未出现改变，说明 newInterval 应该是插入数组开始
             *      - n != -1，说明 n 出现改变， newInterval 应该是插入数组 n 的位置
             *
             * 2 newInterval 和其他范围覆盖，需要合并，m != -1，n：
             *      - n = -1，说明 n 出现改变， newInterval 应该是插入数组 n 的位置
             *      - n != -1，说明 n 未出现改变，合并到了数字最后
             */

            int[][] res;
            if (m == -1) {
                res = new int[intervals.length + 1][2];
                if (n == -1) {
                    System.arraycopy(intervals, 0, res, 0, intervals.length);
                    res[intervals.length] = newInterval;
                } else {
                    System.arraycopy(intervals, 0, res, 0, n);
                    res[n] = newInterval;
                    System.arraycopy(intervals, n, res, n + 1, intervals.length - n);
                }
            } else {
                if (n == -1) {
                    res = Arrays.copyOf(intervals, m + 1);
                } else {
                    res = new int[intervals.length - n + m + 1][2];
                    System.arraycopy(intervals, 0, res, 0, m + 1);
                    System.arraycopy(intervals, n, res, m + 1, intervals.length - n);
                }
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0057_InsertInterval().new Solution();
        int[][] ints = null;

        ints = solution.insert(new int[][]{{6, 8}}, new int[]{1, 5});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(Arrays.toString(ints[i]));
        }
        System.out.println();

        ints = solution.insert(new int[][]{{1, 5}}, new int[]{6, 8});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(Arrays.toString(ints[i]));
        }
        System.out.println();

        ints = solution.insert(new int[][]{{1, 5}, {6, 8}}, new int[]{5, 6});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(Arrays.toString(ints[i]));
        }
        System.out.println();

        ints = solution.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{4, 5});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(Arrays.toString(ints[i]));
        }
        System.out.println();

        ints = solution.insert(new int[][]{{1, 3}, {6, 9}}, new int[]{2, 5});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(Arrays.toString(ints[i]));
        }
        System.out.println();

        ints = solution.insert(new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}, new int[]{4, 8});
        for (int i = 0; i < ints.length; i++) {
            System.out.print(Arrays.toString(ints[i]));
        }
        System.out.println();
    }
}